#include <stdio.h>

void swap(int* x,int* y)
{
	int t=*x;
	*x=*y;
	*y=t;
}

void quick_sort_recursive(int* arr,int start,int end)
{
	if(start>end){
		return ;
	}
	int left=start,right=end-1;
	int min=arr[end];
	while(left<right){
		while(arr[left]<min && left<right)
			left++;
		while(arr[right]>=min && left<right)
			right--;
		swap(&arr[left],&arr[right]);
	}
	if(arr[left]>arr[end]){
		swap(&arr[left],&arr[end]);
	}
	else
		left++;
	if(left){
		quick_sort_recursive(arr,start,end-1);
	}
	quick_sort_recursive(arr,start+1,end);
}

void quick_sort(int* arr,int size)
{
	quick_sort_recursive(arr,0,size-1);
}

int main(void)
{
	
	int arr[]={0,55,8,56,45,2,4,89,100,456};
	quick_sort(arr,sizeof(arr)/sizeof(arr[0]));
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
	{
		printf("%d ",arr[i]);
	}
	
	return 0;
 } 
